package 鸡尾酒排序;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class CocktailSort {
    public static void main(String[] args){
        //鸡尾酒排序算法的测试
     /*   int[] arr = new int[]{11,4,3,54,2,32,45,23,55,15,28,99,100,92,22};
        System.out.println("排序前");
        System.out.println(Arrays.toString(arr));
        int[] newArr=cocktailSort(arr);
        System.out.println("排序后");
        System.out.println(Arrays.toString(newArr));*/
     /***************************以上是鸡尾酒算法测试部分**********************************/
     //鸡尾酒算法时间复杂度的测试
       /* //创建要给80000个的随机的数组
        int[] arr = new int[80000];
        for(int i =0; i < 80000;i++) {
            arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
        }

        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);


        cocktailSort(arr);

        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序后的时间是=" + date2Str);*/
    }

    public static int[] cocktailSort(int[] arr){
        long timeS = System.currentTimeMillis();
        //该算法是只需要向左或右推数组长度的一半次数就够了
        for (int i = 0; i < arr.length / 2; i++){
            //第一个for循环是将数组中最大的数，向最后推。结果最大的数总会在最右边
            //例如上面的数组
            //第一次：5因为最大，所以在执行下面循环之后，一定位于数组最后面。（以此类推，第二次，是4最大，会位于5的前面）
            for (int j = i; j < arr.length - i - 1; j++){
                if (arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
                //如果要测试时间复杂度这一行要注释
               System.out.println("swap biggest number : " + Arrays.toString(arr));
            }
            //第二个循环是将数组中最小的数，往最前面推。结果最小的数总会在最右边
            //例如上面的数组
            //第一次往右，1是最小，循环执行完毕后，1一定位于数组最前面。（类似地，第二次就会把第二小的数字2，向左推到1的后面）
            for (int j = arr.length - 1 - (i + 1); j >= i; j--){
                if (arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
                //如果要测试时间复杂度这一行要注释
                System.out.println("swap smallest number : " + Arrays.toString(arr));
            }
            //当执行完一轮循环之后，向右和向左推的数就不会再参与下一轮的循环了，不然就浪费资源了。
        }
        //如果要测试时间复杂度这一行要注释
        System.out.println("final result : " + Arrays.toString(arr));
        return arr;
    }
}
